# 172. 递增三元组(好题)
# https://www.lanqiao.cn/problems/172/learning/?page=1&first_category_id=1&second_category_id=3
# Date: 2025/2/14
import bisect

from leetcode import test_function


def three_tuple_bf(n: int, matrix):
    """暴力解法， 时间复杂度为O(n^3)
    超时4项"""
    cnt = 0
    for i in range(n):
        for j in range(n):
            if matrix[0][i] < matrix[1][j]:
                for k in range(n):
                    if matrix[1][j] < matrix[2][k]:
                        cnt += 1
    return cnt


def bisect_left(sorted_arr, target: int):
    """
    查找数组中大于 target 的第一个元素的索引。
    """
    left, right = 0, len(sorted_arr) - 1
    res = len(sorted_arr)  # 默认返回数组长度（所有元素都不大于 target 的情况）
    while left <= right:
        mid = left + ((right - left) >> 1)
        if sorted_arr[mid] > target:
            right = mid - 1  # 继续向左寻找更小的候选
            res = mid  # 记录可能的候选索引
        else:
            left = mid + 1  # 向右查找
    return res


def bisect_right(sorted_arr, target: int):
    """
    查找数组中大于等于 target 的第一个元素的索引。
    """
    left, right = 0, len(sorted_arr)
    while left < right:
        mid = left + ((right - left) >> 1)
        if sorted_arr[mid] <= target:
            left = mid + 1  # 继续向右寻找更大的候选
        else:
            right = mid  # 向左查找

    return left


def three_tuple_bisect(n: int, matrix):
    """使用二分查找法
    仍然超时两项"""
    # 排序
    for i in range(3):
        matrix[i].sort()
    res = 0
    # 使用二分法查找
    for i in range(n):
        a = matrix[0][i]
        start_a = bisect_left(matrix[1], a)
        for j in range(start_a, n):
            b = matrix[1][j]
            start_b = bisect_right(matrix[2], b)
            res += (n - start_b)
    return res


def three_tuple_bisect_opt(n: int, matrix):
    """优化的二分查找法(妙)
    注意! 三元问题从中间一层考虑往往更加简单省时间"""
    # 排序
    for i in range(3):
        matrix[i].sort()
    res = 0
    # 使用二分法查找
    for i in range(n):  # 对 B 的每一个元素遍历
        a = bisect.bisect_left(matrix[0], matrix[1][i])  # 统计A中小于B[i]的元素数量
        c = bisect.bisect_right(matrix[2], matrix[1][i])  # 统计C中大于等于B[i]的元素数量
        res += a * (n - c)
    return res


def three_tuple_bf_opt(n: int, matrix):
    """对于三元问题使用中间层的思路, 也可以直接优化暴力法 """
    # 排序
    for i in range(3):
        matrix[i].sort()
    res = 0
    j, k = 0, 0
    for i in range(n):  # 对 B 的每一个元素遍历
        while j < n and matrix[0][j] < matrix[1][i]:  # 统计A中小于B[i]的元素数量
            j += 1
        while k < n and matrix[2][k] <= matrix[1][i]:  # 统计C中大于等于B[i]的元素数量
            k += 1
        res += j * (n - k)
    return res


if __name__ == '__main__':
    # n = int(input())
    # inp = []
    # for i in range(3):
    #     inp.append(list(map(int, input().split())))
    print(bisect.bisect_left([0, 1, 2, 3, 4, 5, 7, 8], 5))
    print(bisect_left([0, 1, 2, 3, 4, 5, 7, 8], 5))
    print(bisect.bisect_right([0, 1, 2, 3, 4, 5, 7, 8], 5))
    print(bisect_right([0, 1, 2, 3, 4, 5, 7, 8], 5))
    arr = []
    with open("../data/172.in", "r") as file:
        n = int(file.readline())
        for i in range(3):
            arr.append(list(map(int, file.readline().split())))

    inp = [{"n": 3, "matrix": [[1, 1, 1], [2, 2, 2], [3, 3, 3]]},
           {"n": 3, "matrix": [[3, 2, 1], [4, 2, 6], [1, 3, 5]]},
           {"n": n, "matrix": arr},
           ]
    out = [27, 5, 169410405]
    test_function(three_tuple_bf, inp[:-1], out[:-1])
    test_function(three_tuple_bisect, inp, out)
    test_function(three_tuple_bisect_opt, inp, out)
    test_function(three_tuple_bf_opt, inp, out)
